import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;


public class AlgoritmPTDF 
{
	
	public static int test(boolean [] viz)
	{
		for(int i=0;i<viz.length;i++)
			if(viz[i] == false)
				return i;
		return -1;
	}
	
	public static String getParcugerePTDF2(GrafOrientat g)
	{
		Stack <Integer> q = new Stack <Integer>();
		boolean [] viz = new boolean [g.getNrVarfuri()];
		String s="";
	
		s+=" 0";
		viz[0] = true;
		q.add(0);
		
		while(test(viz) != -1)
		{
			if(q.isEmpty())
				{
					q.add(test(viz));
					s=s+" "+String.valueOf(test(viz));
					viz[test(viz)] = true;
				}
			
			while(!q.isEmpty())
			{
				int aux = q.peek();
				boolean ok = false;
				
				for(int i=0; i < g.getNrElem(aux) ;i++)
					if(viz[g.getListaAd(aux).get(i)] == false)
					{
						q.add(g.getListaAd(aux).get(i));
						viz[g.getListaAd(aux).get(i)] = true;
						s+=" ";
						s+=g.getListaAd(aux).get(i);
						ok = true;
						break;
					}
				if(ok ==  false)
					q.pop();
			}
		}
		
		return s;
	}
	
	public static String getParcugerePTDF(GrafOrientat g)
	{
		Stack <Integer> q = new Stack <Integer>();
		boolean [] viz = new boolean [g.getNrVarfuri()];
		String s="";
	
		s+=" 0";
		viz[0] = true;
		q.add(0);
	
		
		while(test(viz) != -1)
		{
			if(q.isEmpty())
				{
					q.add(test(viz));
					s=s+" "+String.valueOf(test(viz));
					viz[test(viz)] = true;
				}
			
			while(!q.isEmpty())
			{
				int aux = q.peek();
				boolean ok = false;
				
				for(int i=0; i < g.getNrElem(aux) ;i++)
					if(viz[g.getListaAd(aux).get(i)] == false)
					{
						q.add(g.getListaAd(aux).get(i));
						viz[g.getListaAd(aux).get(i)] = true;
						s+=" ";
						s+=g.getListaAd(aux).get(i);
						ok = true;
						break;
					}
					else
					{
						Stack <Integer> a = new Stack <Integer>();
						a.add(q.peek());
						q.pop();
						if(!q.isEmpty())
						{
							a.add(q.peek());
							q.pop();
							
							while(!q.isEmpty())
							{
								int x = q.peek();
								if(x == g.getListaAd(aux).get(i))
									return "Formeaza ciclu";
								a.add(x);
								q.pop();
							}
						}
						
						while(!a.isEmpty())
						{
							q.add(a.peek());
							a.pop();
						}
					}
				if(ok ==  false)
					q.pop();
			}
		}
		
		return s;
	}
	
}
